In a typical computer graphics display application, a person views an image generated by the display system and displayed on a screen. Conventionally, the image is composed by an array of individual picture-cells ("pixels"). Pixels are the dots of color that define the image. Each of the pixels is defined by characteristics such as color and intensity. Traditionally, pixels are organized into a two-dimensional array or grid defined by raster lines. Each line is drawn by scan displaying the individual pixels along the line. An explanation of images composed of individual pixels is provided in a book Computer Graphics: Principles and Practice, 2nd Edition, Foley, van Dam, Feiner & Hughes, (Reprinted in 1991)(1990), by Addison-Wesley Publishing Company, see the section beginning on page 9.
In practice, rather than defining the characteristics of each pixel, display systems define an image from a collection of primitive graphic shapes such as polygons. The polygons are numerically represented in terms of size, color, location and other characteristics. To accomplish an image, the polygon representations are processed by an image generator producing pixel data signals by a process called polygon rendering. In effect, polygon rendering involves sampling a polygon to calculate how the polygon influences the pixels.
Display systems typically generate each pixel data signal by sampling several locations within the pixel of the polygon. This sampling technique is used to reduce undesirable visual artifacts in the displayed image. These visual artifacts, commonly referred to as aliasing, often appear as jagged lines at the polygon boundaries.
Conventionally, systems that use multiple sampling locations for each pixel treat pixels as square or rectangular regions in the image plane which are subdivided by a grid or array of sub-pixel points. Typically, the regions defined by the sub-pixel points abut their neighbors uniformly in both directions and cover the image plane exactly once. Each point is then considered with regard to each influencing scene detail (polygon) to generate a value for each sub-pixel point. Generally, the final color for a pixel is calculated by combining the sub-pixel values for that pixel. However, some display systems compute the final pixel color from a weighted average of the image information in a two-by-two set of pixels, that is, from four pixels worth of sub-pixel values.
The number of sub-pixels used to generate the final color for each pixel has a direct impact on the cost of the display system. Display systems typically store data for each subpixel in the pixel. Thus, pixel data memory (commonly referred to as "frame buffer" memory) must be allocated for every sub-pixel in every pixel. For example, a graphics system that uses 16 sub-pixels per pixel and has a display with a 1024-by-1024 array of pixels would use over 16 million frame buffer locations for the sub-pixel data. Due to the relatively high cost of frame buffer memory, a need exists for a computer graphics display system that produces anti-aliased images but uses less frame buffer memory.
The present invention provides a novel memory allocation scheme and a novel sub-pixel sampling technique to reduce memory requirements and provide high quality anti-aliased images. The memory allocation scheme involves storing pixel data in the frame buffer on a per-polygon, per-pixel basis rather than storing data for each sub-pixel as discussed above. The sampling technique involves generating pixel data sub-pixels using an interlocking pixel pattern.
Pixel data is stored on a per-polygon, per-pixel basis in the frame buffer by separately storing each polygon that influences a pixel in memory locations allocated for that pixel. For example, if a pixel is influenced by two polygons, the frame buffer will contain two sets of data for the pixel, i.e., one set for each polygon. If another pixel is influenced by only one polygon, the frame buffer will contain only one set of data for that pixel. Thus, for each pixel that is influenced by at least one polygon, one set of polygon data is stored in the frame buffer for each polygon that influences the pixel.
Unlike conventional sub-pixel display systems, the polygons are not blended with other polygons as they are added to the frame buffer. Instead, each polygon that influences the pixel is stored in the frame buffer. The polygons are blended at a later stage in the pixel data generation process.
The per-polygon, per-pixel frame buffer scheme uses less memory because memory is allocated for each polygon that influences a pixel rather than for each sub-pixel associated with the pixel. In practice, each pixel is influenced by relatively few polygons. Thus, less memory is needed to store the polygon information than would be needed to store the subpixel information.
Turning now to the interlocking pixel pattern mentioned above, the pixel pattern is defined by sub-pixel areas, each of which is associated with a sub-pixel. The sub-pixel areas are arrayed so that some of the sub-pixel areas lie outside the area conventionally defined for the pixel and lie within a "hole" defined in the adjacent pixels' pattern. The arrayed sub-pixel areas and the holes are defined so that each part of the image plane is covered by one and only one sub-pixel area. Thus, the sub-pixel areas form a contiguous, non-overlapping tiling of the pixel image plane yet provide a wider sampling area for each pixel.
The interlocking pixel technique can increase the quality of the displayed image by reducing aliasing associated with image problems such as brightness slope discontinuities. Moreover, this technique does not significantly increase system memory requirements and can be implemented with relatively minimal impact on image processing speed.